package 堆;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * @author 帅小伙
 * @date 2021/12/30
 * @description
 */
public class Demo01JZ59滑动窗口的最大值 {


    public static void main(String[] args) {
        Demo01JZ59滑动窗口的最大值 test = new Demo01JZ59滑动窗口的最大值();

        int arr[] = {9,10,9,-7,-3,8,2,-6};
        test.maxInWindows(arr,5);
    }

    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(num.length < size || size <=0){
            return result;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((a,b)->Integer.compare(b,a));
        int l = 0,r = 0;
        for (int i = 0; i < num.length; i++) {
            if(r<size-1){
                queue.add(num[i]);
                r++;
            }else{
                int max = queue.peek();
                result.add(max);
                if(num[l] == max){
                    queue.poll();
                }else{
                }
                queue.add(num[i]);
                r++;
                l++;
            }
        }
        result.add(queue.peek());

        return result;
    }
}
